#pragma once

#include <vector>
#include <memory>
#include <iostream>

using namespace std;

struct Edge {
	int from_;
	int to_;
	Edge(int from, int to) : from_(from), to_(to) {}
	
	bool operator < (const Edge edge) const {
		return (edge.from_ > from_ || (edge.from_ == from_ && edge.to_ > to_));
	}

	bool operator == (const Edge edge) const {
		return (edge.from_ == from_  && edge.to_ == to_);
	}
};

class IGraph {
public:
	virtual int getNumberOfVertices() const = 0;
	virtual vector<int> getIncidenceList(int vertex) const = 0;
	virtual ~IGraph() {};
};

class MatrixGraph : public IGraph {
public:
	MatrixGraph(const vector<Edge> &edgesList, int verticesNumber) : 
		verticesNumber_(verticesNumber), edgesNumber_(edgesList.size()),
		incidenceMatrix_(verticesNumber, vector<bool>(verticesNumber, false)) {
		
		for (const auto& edge : edgesList) {
			incidenceMatrix_[edge.from_][edge.to_] = 1;
		}
	}

	int getNumberOfVertices() const {
		return verticesNumber_;
	}

	vector<int> getIncidenceList(int vertex) const {
		vector<int> incidenceList;
		for (size_t i = 0; i < incidenceMatrix_[vertex].size(); ++i) {
			if (incidenceMatrix_[vertex][i]) 
				incidenceList.push_back(i);
		}
		return incidenceList;
	}

private:
	int verticesNumber_;
	int edgesNumber_;
	vector< vector<bool> > incidenceMatrix_;
};

class IncidenceListGraph : public IGraph {
public:
	IncidenceListGraph(const vector<Edge> &edgesList, int verticesNumber) : verticesNumber_(verticesNumber), edgesNumber_(edgesList.size()), 
		incidenceList_(verticesNumber) {
		for (const auto& edge : edgesList) {
			incidenceList_[edge.from_].push_back(edge.to_);
		}
	}

	int getNumberOfVertices() const {
		return verticesNumber_;
	}
	
	vector<int> getIncidenceList(int vertex) const {
		return incidenceList_[vertex];
	}

private:
	int verticesNumber_;
	int edgesNumber_;
	vector< vector<int> > incidenceList_;
};

inline unique_ptr<IGraph> makeCompactGraph(const vector<Edge> &edgesList, int verticesNumber) {
	unique_ptr<IGraph> matrixGraph(new MatrixGraph(edgesList, verticesNumber));
	unique_ptr<IGraph> incidenceListGraph(new IncidenceListGraph(edgesList, verticesNumber));

	if ((size_t)(verticesNumber * verticesNumber) < edgesList.size() * sizeof(int))
		return matrixGraph;
	else
		return incidenceListGraph;
}